{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Last Moment Before All Ants Fall Out of a Plank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #brainteaser #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #脑筋急转弯 #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getLastMoment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #所有蚂蚁掉下来前的最后一刻"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一块木板，长度为 <code>n</code> 个 <strong>单位</strong> 。一些蚂蚁在木板上移动，每只蚂蚁都以 <strong>每秒一个单位</strong> 的速度移动。其中，一部分蚂蚁向 <strong>左</strong> 移动，其他蚂蚁向 <strong>右</strong> 移动。</p>\n",
    "\n",
    "<p>当两只向 <strong>不同</strong> 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。</p>\n",
    "\n",
    "<p>而当蚂蚁在某一时刻 <code>t</code> 到达木板的一端时，它立即从木板上掉下来。</p>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> 和两个整数数组 <code>left</code> 以及 <code>right</code> 。两个数组分别标识向左或者向右移动的蚂蚁在 <code>t = 0</code> 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/06/17/ants.jpg\" style=\"height: 610px; width: 450px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, left = [4,3], right = [0,1]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>如上图所示：\n",
    "-下标 0 处的蚂蚁命名为 A 并向右移动。\n",
    "-下标 1 处的蚂蚁命名为 B 并向右移动。\n",
    "-下标 3 处的蚂蚁命名为 C 并向左移动。\n",
    "-下标 4 处的蚂蚁命名为 D 并向左移动。\n",
    "请注意，蚂蚁在木板上的最后时刻是 t = 4 秒，之后蚂蚁立即从木板上掉下来。（也就是说在 t = 4.0000000001 时，木板上没有蚂蚁）。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/06/17/ants2.jpg\" style=\"height: 101px; width: 639px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7, left = [], right = [0,1,2,3,4,5,6,7]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>所有蚂蚁都向右移动，下标为 0 的蚂蚁需要 7 秒才能从木板上掉落。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/06/17/ants3.jpg\" style=\"height: 100px; width: 639px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7, left = [0,1,2,3,4,5,6,7], right = []\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>所有蚂蚁都向左移动，下标为 7 的蚂蚁需要 7 秒才能从木板上掉落。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10^4</code></li>\n",
    "\t<li><code>0 &lt;= left.length &lt;= n + 1</code></li>\n",
    "\t<li><code>0 &lt;= left[i] &lt;= n</code></li>\n",
    "\t<li><code>0 &lt;= right.length &lt;= n + 1</code></li>\n",
    "\t<li><code>0 &lt;= right[i] &lt;= n</code></li>\n",
    "\t<li><code>1 &lt;= left.length + right.length &lt;= n + 1</code></li>\n",
    "\t<li><code>left</code> 和 <code>right</code> 中的所有值都是唯一的，并且每个值 <strong>只能出现在二者之一</strong> 中。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [last-moment-before-all-ants-fall-out-of-a-plank](https://leetcode.cn/problems/last-moment-before-all-ants-fall-out-of-a-plank/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [last-moment-before-all-ants-fall-out-of-a-plank](https://leetcode.cn/problems/last-moment-before-all-ants-fall-out-of-a-plank/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[4,3]\\n[0,1]', '7\\n[]\\n[0,1,2,3,4,5,6,7]', '7\\n[0,1,2,3,4,5,6,7]\\n[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        a = max(left) if left else -inf\n",
    "        b =  n-min(right) if right else -inf\n",
    "        return max(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "class Solution:\r\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\r\n",
    "        return max(max(left) if left else 0, n - min(right) if right else 0)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        if not left and not right:\n",
    "            return 0\n",
    "        left.sort()\n",
    "        right.sort()\n",
    "        if not right:\n",
    "            return left[-1]\n",
    "        if not left:\n",
    "            return n - right[0]\n",
    "        return max(n - right[0], left[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        ans=0\n",
    "        if left:\n",
    "            ans = max(left)\n",
    "        if right:\n",
    "            ans = max(ans,n-min(right))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        left_time = 0\n",
    "        right_time = 0\n",
    "        if left:\n",
    "            left.sort()\n",
    "            left_time = left[-1]\n",
    "        if right:\n",
    "            right.sort()\n",
    "            right_time = n - right[0]\n",
    "        return max(left_time, right_time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        left_max = max(left) if left else 0\n",
    "        right_min = min(right) if right else n\n",
    "\n",
    "        return max(n - right_min, left_max)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        l = 0 if not left else max(left)\n",
    "        if right:\n",
    "            l = max(l, n - min(right))\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        maxPos=max(left) if left else 0\n",
    "        minPos=min(right) if right else n\n",
    "        return max(maxPos,n-minPos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        ans = 0\n",
    "        if len(left) > 0:\n",
    "            ans = max(left)\n",
    "        if len(right) > 0:\n",
    "            ans = max(ans,n-min(right))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        ans = 0 if not left else max(left)\n",
    "        if right:\n",
    "            ans = max(ans, max(n - ant for ant in right))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        a = 0\n",
    "        if left:\n",
    "            a = max(left)\n",
    "        if right:\n",
    "            a = max(a, max(n-i for i in right))\n",
    "        return a\n",
    "        # return max([max(left),n-min(right)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        ans=0\n",
    "        for l in left:\n",
    "            ans=max(ans,l)\n",
    "        for r in right:\n",
    "            ans=max(ans,n-r)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        if left and right:\n",
    "            return max(max(left), n - min(right))\n",
    "        elif left and not right:\n",
    "            return max(left)\n",
    "        else:\n",
    "            return n - min(right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for x in left:\n",
    "            if x > ans:\n",
    "                ans = x\n",
    "        for x in right:\n",
    "            if n-x>ans:\n",
    "                ans = n-x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        if len(left)==0 and len(right) == 0:\n",
    "            return 0\n",
    "        if len(left)==0:\n",
    "            return n-min(right)\n",
    "        if len(right)==0:\n",
    "            return max(left)\n",
    "        \n",
    "        return max(max(left),n-min(right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        mx = -inf\n",
    "        if left:\n",
    "            mx = max(max(left), mx)\n",
    "        if right:\n",
    "            mx = max(n - min(right), mx)\n",
    "        return mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        if left == []:\n",
    "            return n - min(right)\n",
    "        if right == []:\n",
    "            return max(left)\n",
    "        t1 = max(left)\n",
    "        t2 = n - min(right)\n",
    "        return max(t1,t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        if len(left)!=0 and len(right)!=0:\n",
    "            n1 = min(right)\n",
    "            n2 = max(left)\n",
    "            print(n1,n2)\n",
    "            if (n-n1)>=n2:\n",
    "                return n-n1\n",
    "            else:\n",
    "                return n2\n",
    "        elif len(left)==0:\n",
    "            n3 = min(right)\n",
    "            print(n3)\n",
    "            return n-n3\n",
    "        elif len(right)==0:\n",
    "            n4 = max(left)\n",
    "            print(n4)\n",
    "            return n4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        lastMoment = 0 if not left else max(left)\n",
    "        if right:\n",
    "            lastMoment = max(lastMoment, max(n - ant for ant in right))\n",
    "        return lastMoment\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        return max(max(left or [0]), n-min(right or [n]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        return max(max(left, default=0), max((n - x for x in right), default=0))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        if not left and not right:\n",
    "            return 0\n",
    "        if not left:\n",
    "            return max(n - x for x in right)\n",
    "        if not right:\n",
    "            return max(left)\n",
    "        return max(left + [n - x for x in right])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        if len(left) == 0 and len(right) == 0:\n",
    "            return 0\n",
    "        if len(left) == 0:\n",
    "            return n - min(right)\n",
    "        if len(right) == 0:\n",
    "            return max(left)\n",
    "\n",
    "        l = max(left)\n",
    "        r = min(right)\n",
    "        return max(l, n-r)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        #print(min(left) if left else 0, max(right) if right else 0)\n",
    "        return max(n - min(right) if right else 0, max(left) if left else 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for x in left:\n",
    "            ans = max(x, ans)\n",
    "        for x in right:\n",
    "            ans = max(n-x, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        if not left:\n",
    "            return n - min(right)\n",
    "        elif not right:\n",
    "            return max(left)\n",
    "        else:\n",
    "            return max(max(left), n - min(right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        ans = 0\n",
    "        if left:\n",
    "            ans = max(ans, max(i for i in left))\n",
    "        if right:\n",
    "            ans = max(ans, max(n - i for i in right))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        left.sort()\n",
    "        right.sort()\n",
    "        if len(left) == 0:\n",
    "            return n - right[0]\n",
    "        elif len(right) == 0:\n",
    "            return left[-1]\n",
    "        else:\n",
    "            return max(left[-1], n - right[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        return max(max(left + [0]), n - min(right + [n]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        lastMoment = 0 if not left else max(left)\n",
    "        if right:\n",
    "            lastMoment = max(lastMoment, max(n - ant for ant in right))\n",
    "        return lastMoment\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        ans = 0\n",
    "        if len(left) > 0:\n",
    "            ans = max(ans, max(left))\n",
    "        if len(right) > 0:\n",
    "            ans = max(ans, n - min(right))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        return max(0 if left==[] else max(left),0 if right ==[] else n-min(right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "\n",
    "        lmax= max(left) if left else 0 \n",
    "        rmin = min(right) if right else n \n",
    "\n",
    "        return max(lmax,n-rmin)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int: \n",
    "        ans = max(left) if left else 0\n",
    "        ans = max(max(n - x for x in right), ans) if right else ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        res = 0\n",
    "        for index in left:\n",
    "            res = max(res,index)\n",
    "        for index in right:\n",
    "            res = max(res, n-index)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        if left and right:\n",
    "            return max(max(left), n-min(right))\n",
    "        elif left:\n",
    "            return max(left)\n",
    "        else:\n",
    "            return n-min(right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        maxLeft = max(left) if left else 0\n",
    "        minRight = n - min(right) if right else 0\n",
    "        return max(maxLeft, minRight)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        lastMoment = 0 if not left else max(left)\n",
    "        if right:\n",
    "            lastMoment = max(lastMoment, max(n - ant for ant in right))\n",
    "        return lastMoment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        res = 0\n",
    "        if left:\n",
    "            res = max(left)\n",
    "        if right:\n",
    "            res = max(res, n - min(right))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        return max(max(left, default=-1), max([n - r for r in right], default=-1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        if left!=[] and right!=[]:\n",
    "            return max(max(left), n-min(right))\n",
    "        elif left:\n",
    "            return max(left)\n",
    "        else:\n",
    "            return n-min(right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        # /* Brainteaser\n",
    "        #  *  最後一隻螞蟻從木板上掉下來的時刻，所以並不需要區分每隻螞蟻。\n",
    "        #  *  由於改變移動方向不花費額外時間，而且改變移動方向後的移動速度不變。\n",
    "        #  *  因此，兩隻相遇的螞蟻同時改變移動方向之後的情形等價於兩隻螞蟻都不改變移動方向，繼續以原來的方向和速度移動。\n",
    "        #  *  這樣問題就簡化成根據每隻螞蟻的初始位置和移動方向得到最後一隻螞蟻到達木板邊界的時刻。\n",
    "        #  *  假設一隻螞蟻在位置 p。\n",
    "        #  *  如果這隻螞蟻向左移動，則它到達木板邊界所需的時間是 p。\n",
    "        #  *  如果這隻螞蟻向右移動，則它到達木板邊界所需的時間是 n−p。\n",
    "        #  */\n",
    "        for p in left:\n",
    "            retVal = max(retVal, p)\n",
    "        for p in right:\n",
    "            retVal = max(retVal, n - p)\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        res = 0\n",
    "        for x in left:\n",
    "            res = max(res, x)\n",
    "        for x in right:\n",
    "            res = max(res, n - x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        max_time = 0\n",
    "        \n",
    "        if left:\n",
    "            max_time = max(max_time, max(left))\n",
    "        if right:\n",
    "            max_time = max(max_time, n - min(right))\n",
    "        \n",
    "        return max_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        if not left:\n",
    "            last = 0\n",
    "        else:\n",
    "            last = max(left)\n",
    "        if right:\n",
    "            last = max(last, max(n - num for num in right))\n",
    "        return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        maxL = -1 if not left else max(left)\n",
    "        minR = -1 if not right else min(right)\n",
    "        ans = 0\n",
    "        if maxL != -1:\n",
    "            ans = max(maxL, ans)\n",
    "        if minR != -1:\n",
    "            ans = max(n - minR, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        return max(max(left, default=0), n - min(right, default=n))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        return max(max(left) if left else 0,\n",
    "                   n-min(right) if right else 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        l = max(left, default=0)\n",
    "        r = n - min(right, default=n)\n",
    "        return max(l, r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        return max(max(left, default=0), n-min(right, default=n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        return max(max(left, default=0), n - min(right, default=n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# File       : Q1503.py\n",
    "# Time       ：2023/8/14 20:32\n",
    "# Author     ：author name\n",
    "# version    ：python 3\n",
    "# Description：\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "有一块木板，长度为 n 个 单位 。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。其中，一部分蚂蚁向 左 移动，其他蚂蚁向 右 移动。\n",
    "\n",
    "当两只向 不同 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。\n",
    "\n",
    "而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。\n",
    "\n",
    "给你一个整数 n 和两个整数数组 left 以及 right 。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        l_max = 0\n",
    "        if left:\n",
    "            l_max = max(left)\n",
    "        r_min = n\n",
    "        if right:\n",
    "            r_min = min(right)\n",
    "        return max(l_max, n - r_min)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        \"\"\"\n",
    "            tips :\n",
    "                碰撞后  蚂蚁们都不改变 方向\n",
    "        \"\"\"\n",
    "        l = min(right) if right else n \n",
    "        r = max(left) if left else 0 \n",
    "        return max(r,n-l)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        return max(left + [n - x for x in right])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(left)):\n",
    "            res = max(res, left[i])\n",
    "\n",
    "        for i in range(len(right)):\n",
    "            res = max(res, n-right[i])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for x in left:\n",
    "            ans = max(x, ans)\n",
    "        for x in right:\n",
    "            ans = max(n - x, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        ans=0\n",
    "        if left!=[]:\n",
    "            ans=max(ans,max(left))\n",
    "        if right!=[]:\n",
    "            ans=max(ans,n-min(right))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        left.sort() \n",
    "        right.sort() \n",
    "        ans = 0 \n",
    "        if left:\n",
    "            ans = max(ans, left[-1])\n",
    "        if right:\n",
    "            ans = max(ans, n - right[0])\n",
    "        return ans \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        left.append(0)\n",
    "        right.append(n)\n",
    "        return max(n - min(right), max(left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        LastMoment=0 if not left else max(left)\n",
    "        if right :\n",
    "            LastMoment=max(LastMoment,max(n-ant for ant in right))\n",
    "        return LastMoment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        res = max(left) if left else 0\n",
    "        res = max(max(n - r for r in right), res) if right else res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        ans = 0\n",
    "        if left:\n",
    "            ans = max(ans, max(left))\n",
    "        if right:\n",
    "            ans = max(ans, n - min(right))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        l = max(left + [0])\n",
    "        r = min(right + [n])\n",
    "\n",
    "        return max(l, n - r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(left)):\n",
    "            ans = max(ans, left[i])\n",
    "        for i in range(len(right)):\n",
    "            ans = max(ans, n - right[i])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        res=0\n",
    "        for i in left:\n",
    "            res=max(res,i)\n",
    "        for i in right:\n",
    "            res=max(res,n-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        for i in range(len(right)):\n",
    "            right[i] = n - right[i]\n",
    "        return max(left + right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        ans = 0\n",
    "        if left:\n",
    "            ans = max(ans, max(left))\n",
    "        if right:\n",
    "            ans = max(ans, max([n-i for i in right]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        if right is None or left is None:\n",
    "            return len(right)-1 if right else len(left)-1\n",
    "        max_right,max_left=0,0\n",
    "        for rig_dis in right:\n",
    "            max_right=max(n-rig_dis,max_right)\n",
    "        for left_dis in left:\n",
    "            max_left=max(max_left,left_dis)\n",
    "        ans=max(max_left,max_right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        for x in right:\n",
    "            left.append(n - x)\n",
    "        return max(left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        return max(left+[n-r for r in right])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        if right is None or left is None:\n",
    "            return len(right)-1 if right else len(left)-1\n",
    "        max_right,max_left=0,0\n",
    "        for rig_dis in right:\n",
    "            max_right=max(n-rig_dis,max_right)\n",
    "        for left_dis in left:\n",
    "            max_left=max(max_left,left_dis)\n",
    "        return max(max_right,max_left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\r\n",
    "        len_left = len(left)\r\n",
    "        len_right = len(right)\r\n",
    "        if len_right == len_left == 0:\r\n",
    "            return 0\r\n",
    "        if len_left == 0:\r\n",
    "            return n - min(right)\r\n",
    "        if len_right == 0:\r\n",
    "            return max(left)\r\n",
    "        \r\n",
    "        return max(max(left), n - min(right))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        right_time = [n-i for i in right]\n",
    "        a = right_time+left\n",
    "        res = max(a)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        return max(left + [n-r for r in right])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        if left!=[]:\n",
    "            m=max(left)\n",
    "        else:\n",
    "            m=0\n",
    "        if right!=[]:\n",
    "            k=n-min(right)\n",
    "        else:\n",
    "            k=0\n",
    "        return max(m,k)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        # ----------------n\n",
    "        l=max(left+[0])\n",
    "        r=max([n-c for c in right]+[0])\n",
    "        return max(l,r)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        # 如果判定下一秒发生碰撞，则设置两个蚂蚁下一秒开始的方向和位置和现在是相反的\n",
    "        # 两种碰撞情况，相距1格相向，和相距2格相向\n",
    "        # \n",
    "        dis = [0 for _ in range(n+1)]\n",
    "        for item in left:\n",
    "            dis[item] = item - 0 + 1 - 1\n",
    "        for item in right:\n",
    "            dis[item] = n + 1 - item - 1\n",
    "        return max(dis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        left.extend(n-r for r in right)\n",
    "        return max(left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:\n",
    "        return max(left + [n - x for x in right])\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
